Computer graphic systems, including graphic printers, define pictures in a world coordinate system. This can be any Cartesian coordinates system that a user finds convenient. Pictures defined in world coordinates are then mapped by the graphic system into device coordinates, where the device may be for example, a computer screen or a printed page. Typically, a graphic system allows a user to specify which area of the picture definition is to be displayed and where it is to be placed on the display device. A single area can be chosen for display, or several areas can be selected. These areas can be placed in separate display locations, or one area can serve as a small insert into a larger area. This transformation process involves operations for transformation and scaling selected areas and for deleting picture parts outside the areas. These operations are referred to as windowing and clipping.
A rectangle area specified in world coordinates is called a window. The rectangular area on the display device to which a window is mapped is called a viewport. By changing the position of the viewport, objects can be displayed at different positions on an output device, Also, by varying the size of the viewport, the size and proportions of an object can be changed. When different sized windows are successively mapped onto a viewport, zooming effects can be achieved. As the windows are made smaller, a user can zoom in on some part of a scene to view details that are not shown with the larger windows. Similarly, more overview is obtained by zooming out from a section of a scene with successively larger windows. Panning effects are produced by moving a fixed-sized window across a larger picture.
Mapping a window onto a viewport results in the display of only the picture parts within the window. Everything outside the windowing is discarded. Procedures for eliminating all parts of a defined picture outside of specified boundaries are referred to as clipping.
Clipping procedures are generally classified as either a line clipper or a polygon clipper. A line clipper determines which lines are wholly within the window boundaries and which lines are to be totally or partially clipped. For lines that are to be partially clipped, the intersection points with the window boundaries must be calculated. Because a picture may contain thousands of line segments, the clipping process should be performed as efficiently as possible. One such line clipper was developed by Cohen and Sutherland. Another line clipper was developed by Liang and Barsky. Both these line clippers are known in the art of computer graphics.
Hollow polygons used in line drawing applications can be clipped by processing each component line through the line clipper. A polygon processed in this way is reduced to a series of clipped lines. When a polygon boundary defines a fill area, a modified version of the line clipping process is needed because the clipped polygon must remain a closed object. In this case, one or more areas must be produced to define the boundaries for area fill.
One technique for polygon clipping, developed by Sutherland and Hodgman, performs clipping by comparing a polygon to each window boundary in turn. The output of this process is a set of vertices defining the clipped area that is to be filled with a color or shading. See, I. E. Sutherland and G. W. Hodgman "Reentrant Polygon Clipping," Communication of the ACM, 17, 1, 32-42 (Jan. 1974).
Another technique for polygon clipping, developed by Liang and Barsky, performs clipping by expressing each edge as a parametric equation. Using this notation, the possible contributions that can be provided to the output polygon by a particular edge of the input polygon are enumerated. See, You-Dong Liang and Brian A. Barsky "An Analysis and Algorithm for Polygon Clipping," Communication of the ACM, 26, 11,868-877 (Nov. 1983) herein incorporated by reference. One advantage to the Liang and Barsky process is that arbitrarily shaped windows could be processed by using parametric line equations to describe both the window boundaries and the boundaries of the areas to be clipped. Another significant advantage to the Liang and Barsky process is its speed in rectangular clipping.
Both of the aforementioned polygon clipping processes produce a degenerate, or extraneous, edge when a concave polygon is clipped against a rectangular window. With a concave polygon, the output polygon may actually represent two or more distinct polygons. Because these polygon clipping processes produce only one list of vertices, these separate areas will be joined with connecting lines.
Weiler and Atherton have developed a process of polygon clipping that does not create extraneous lines. See, K. Weiler and P. Atherton, "Hidden Surface Removal Using polygon Area Sorting," SID-GRAPH '77 proceedings, Computer Graphics, 11, 2 214-222 (Summer 1977). However, the procedure is unnecessarily complex because of its ability to handle arbitrarily shaped windows. Many applications, particularly laser printing, must complete polygon clipping as quickly as possible. For these applications the Weiler process is not acceptable.
Therefore the primary purpose of the present invention is to provide a method to quickly remove any extraneous edges produced by a polygon clipping process.